import java.util.Arrays;

public class Leetcode {
}

//leetcode:509:斐波那契数列
class Solution1 {
    int[] nums;
    public int fib(int n) {
        nums = new int[31];
        Arrays.fill(nums,-1);
        return dfs(n);
    }

    public int dfs(int n){
        if(nums[n] != -1){
            return nums[n];
        }

        if(n == 0 || n == 1){
            nums[n] = n;
            return n;
        }

        nums[n] = dfs(n-1)+dfs(n-2);
        return nums[n];
    }
}

//leetcode:62:不同路径
//记忆化搜索
class Solution2 {
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m+1][n+1];
        return dfs(m,n,memo);
    }

    public int dfs(int i,int j,int[][] memo){
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        if(i == 0 || j == 0) return 0;
        if(i == 1 && j == 1) return 1;

        memo[i][j] = dfs(i-1,j,memo) + dfs(i,j-1,memo);
        return memo[i][j];
    }
}

//动态规划
class Solution3 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[1][1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(i == 1 && j == 1) continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
}

//leetcode:300:最长递增子序列
//记忆化搜索
class Solution4 {
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        int n = nums.length;
        int[] memo = new int[n];
        for(int i = 0; i < n;i++){
            ret = Math.max(ret,dfs(nums,i,memo));
        }
        return ret;
    }

    public int dfs(int[] nums,int i,int[] memo){
        if(memo[i] != 0){
            return memo[i];
        }
        int ret = 1;
        for(int j = i+1; j < nums.length; j++){
            if(nums[j] > nums[i]){
                ret = Math.max(ret,dfs(nums,j,memo)+1);
            }
        }
        memo[i] = ret;
        return ret;
    }
}

//动态规划
class Solution5 {
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i = n-1; i >= 0;i--){
            for(int j = i+1; j < n;j++){
                if(nums[j] > nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}

//leetcode:375:猜数字大小II
class Solution6 {
    public int getMoneyAmount(int n) {
        int[][] enmo = new int[n+1][n+1];
        return dfs(1,n,enmo);
    }

    public int dfs(int left,int right,int[][] enmo){
        if(left >= right) return 0;
        if(enmo[left][right] != 0) return enmo[left][right];
        int ret = Integer.MAX_VALUE;
        for(int i = left; i <= right; i++){
            int x = dfs(left,i-1,enmo);
            int y = dfs(i+1,right,enmo);
            ret = Math.min(ret,Math.max(x,y)+i);
        }
        enmo[left][right] = ret;
        return ret;
    }
}

//leetcode:329:矩阵中的最长递增路径
class Solution7 {
    int m,n;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        if(m == 0) return 0;
        n = matrix[0].length;
        int ret = 0;
        int[][] memo = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n;j++){
                ret = Math.max(ret,dfs(matrix,i,j,memo));
            }
        }
        return ret;
    }

    public int dfs(int[][] matrix,int i,int j,int[][] memo){
        if(memo[i][j] != 0) return memo[i][j];
        int ret = 1;
        for(int k = 0; k < 4;k++){
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = Math.max(ret,dfs(matrix,x,y,memo)+1);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
}